package crosslinks

// Point 表示一个二维坐标点
type Point struct {
	X, Y float32
}

// Entity 表示游戏中的一个实体接口
type Entity interface {
	GetPosition() Point
	SetPosition(p Point)
	SetLinkNode(node *CrossLinkNode)
	GetLinkNode() *CrossLinkNode
}

// AOIEntity 表示具体的实体结构体
type AOIEntity struct {
	Pos  Point
	Node *CrossLinkNode
}

// GetPosition 返回实体的位置
func (e *AOIEntity) GetPosition() Point {
	return e.Pos
}

// SetPosition 设置实体的位置
func (e *AOIEntity) SetPosition(p Point) {
	e.Pos = p
}

func (e *AOIEntity) SetLinkNode(node *CrossLinkNode) {
	e.Node = node
}

func (e *AOIEntity) GetLinkNode() *CrossLinkNode {
	return e.Node
}

// CrossLinkNode 表示十字链表中的一个节点
type CrossLinkNode struct {
	Entity Entity
	XPrev  *CrossLinkNode
	XNext  *CrossLinkNode
	YPrev  *CrossLinkNode
	YNext  *CrossLinkNode
}

// Grid 表示AOI网格
type Grid struct {
	Xnodes *CrossLinkNode
	Ynodes *CrossLinkNode
	Width  int
	Height int
}

// NewGrid 创建一个新的十字链表网格
func NewGrid(width, height int) *Grid {
	return &Grid{
		Width:  width,
		Height: height,
	}
}

// AddEntity 将实体添加到网格中
func (g *Grid) AddEntity(e Entity) {
	if e == nil {
		return
	}
	x := e.GetPosition().X
	y := e.GetPosition().Y
	if x < 0 || x >= float32(g.Width) || y < 0 || y >= float32(g.Height) {
		return
	}
	node := &CrossLinkNode{Entity: e}
	e.SetLinkNode(node)
	if g.Xnodes == nil {
		g.Xnodes = node
	} else {
		current := g.Xnodes
		for current != nil {
			if current.Entity.GetPosition().X < x {
				if current.XNext != nil {
					current = current.XNext
					continue
				} else {
					current.XNext = node
					node.XPrev = current
					break
				}
			}
			node.XNext = current
			node.XPrev = current.XPrev
			if current.XPrev != nil {
				current.XPrev.XNext = node
			}
			current.XPrev = node
			if current == g.Xnodes {
				g.Xnodes = node
			}
			break
		}
	}
	if g.Ynodes == nil {
		g.Ynodes = node
	} else {
		current := g.Ynodes
		for current != nil {
			if current.Entity.GetPosition().Y < y {
				if current.YNext != nil {
					current = current.YNext
					continue
				} else {
					current.YNext = node
					node.YPrev = current
					break
				}
			}
			node.YNext = current
			node.YPrev = current.YPrev
			if current.YPrev != nil {
				current.YPrev.YNext = node
			}
			current.YPrev = node
			if current == g.Ynodes {
				g.Ynodes = node
			}
			break
		}
	}
}

// RemoveEntity 从网格中移除实体
func (g *Grid) RemoveEntity(e Entity) {
	node := e.GetLinkNode()
	if node == nil {
		return
	}
	//移除X轴
	if node.XPrev != nil {
		node.XPrev.XNext = node.XNext
		if node.XNext != nil {
			node.XNext.XPrev = node.XPrev
		}
	} else {
		g.Xnodes = node.XNext
		node.XNext.XPrev = nil
	}
	//移除Y轴
	if node.YPrev != nil {
		node.YPrev.YNext = node.YNext
		if node.YNext != nil {
			node.YNext.YPrev = node.YPrev
		}
	} else {
		g.Ynodes = node.YNext
		node.YNext.YPrev = nil
	}
}

// MoveEntity 移动实体到新位置
func (g *Grid) MoveEntity(e Entity, newPos Point) {
	node := e.GetLinkNode()
	if node == nil {
		return
	}
	// x轴移动
	//判断是否超出x轴范围
	if newPos.X < 0 || newPos.X >= float32(g.Width) {
		return
	}

	x := newPos.X
	y := newPos.Y
	// 检查左移动还是右移动
	if x < e.GetPosition().X {
		prev := node.XPrev
		if prev != nil {
			findNode := false
			for {
				if prev.Entity.GetPosition().X > x {
					prev = prev.XPrev
					findNode = true
					if prev == nil {
						break
					}
					continue
				}
				break
			}
			if findNode {
				node.XPrev.XNext = node.XNext
				if node.XNext != nil {
					node.XNext.XPrev = node.XPrev
				}
				if prev == nil {
					node.XPrev = nil
					node.XNext = g.Xnodes
					g.Xnodes.XPrev = node
					g.Xnodes = node
				} else {
					node.XPrev = prev
					node.XNext = prev.XNext
					if prev.XNext != nil {
						prev.XNext.XPrev = node
					}
					prev.XNext = node
				}
			}
		}
	} else {
		next := node.XNext
		oldnext := next
		if next != nil {
			findNode := false
			for {
				if next.Entity.GetPosition().X < x {
					findNode = true
					newNext := next.XNext
					if newNext == nil {
						break
					}
					next = newNext
					continue
				}
				break
			}
			if findNode {
				if node.XPrev != nil {
					node.XPrev.XNext = node.XNext
				}
				if node.XNext != nil {
					node.XNext.XPrev = node.XPrev
				}
				node.XPrev = next
				node.XNext = next.XNext
				if next.XNext != nil {
					next.XNext.XPrev = node
				}
				next.XNext = node
				if node == g.Xnodes {
					g.Xnodes = oldnext
				}
			}
		}
	}
	//检测上移还是下移
	if y < e.GetPosition().Y {
		prev := node.YPrev
		if prev != nil {
			findNode := false
			for {
				if prev.Entity.GetPosition().Y > y {
					prev = prev.YPrev
					findNode = true
					if prev == nil {
						break
					}
					continue
				}
				break
			}
			if findNode {
				node.YPrev.YNext = node.YNext
				if node.YNext != nil {
					node.YNext.YPrev = node.YPrev
				}
				if prev == nil {
					node.YPrev = nil
					node.YNext = g.Ynodes
					g.Ynodes.YPrev = node
					g.Ynodes = node
				} else {
					node.YPrev = prev
					node.YNext = prev.YNext
					if prev.YNext != nil {
						prev.YNext.YPrev = node
					}
					prev.YNext = node
				}
			}
		}
	} else {
		next := node.YNext
		oldnext := next
		if next != nil {
			findNode := false
			for {
				if next.Entity.GetPosition().Y < y {
					newNext := next.YNext
					findNode = true
					if newNext == nil {
						break
					}
					next = newNext
					continue
				}
				break
			}
			if findNode {
				if node.YPrev != nil {
					node.YPrev.YNext = node.YNext
				}
				if node.YNext != nil {
					node.YNext.YPrev = node.YPrev
				}
				node.YPrev = next
				node.YNext = next.YNext
				if next.YNext != nil {
					next.YNext.YPrev = node
				}
				next.YNext = node
				if node == g.Ynodes {
					g.Ynodes = oldnext
				}
			}
		}
	}
	e.SetPosition(newPos)
	e.GetLinkNode().Entity = e
}

// GetEntitiesInRange 查询某个区域内的实体
func (g *Grid) GetEntitiesInRange(entity Entity, radius int) []Entity {
	var entities []Entity
	node := entity.GetLinkNode()
	if node == nil {
		return entities
	}
	//找到x轴范围的节点左边的节点
	lxcurrent := node
	xlinks := make([]*CrossLinkNode, 0)
	for {
		if lxcurrent.XPrev != nil {
			if lxcurrent.XPrev.Entity.GetPosition().X < entity.GetPosition().X-float32(radius) {
				break
			}
			lxcurrent = lxcurrent.XPrev
			xlinks = append(xlinks, lxcurrent)
			continue
		}
		break
	}
	//找到x轴范围的节点右边的节点
	rxcurrent := node
	for {
		if rxcurrent.XNext != nil {
			if rxcurrent.XNext.Entity.GetPosition().X > entity.GetPosition().X+float32(radius) {
				break
			}
			rxcurrent = rxcurrent.XNext
			xlinks = append(xlinks, rxcurrent)
			continue
		}
		break
	}
	//找到y轴范围的上边节点
	lycurrent := node
	ylinks := make([]*CrossLinkNode, 0)
	for {
		if lycurrent.YPrev != nil {
			if lycurrent.YPrev.Entity.GetPosition().Y < entity.GetPosition().Y-float32(radius) {
				break
			}
			lycurrent = lycurrent.YPrev
			ylinks = append(ylinks, lycurrent)
			continue
		}
		break
	}
	//找到y轴范围的下边节点
	rycurrent := node
	for {
		if rycurrent.YNext != nil {
			if rycurrent.YNext.Entity.GetPosition().Y > entity.GetPosition().Y+float32(radius) {
				break
			}
			rycurrent = rycurrent.YNext
			ylinks = append(ylinks, rycurrent)
			continue
		}
		break
	}
	//取ylinks和xlinks的交集
	for _, xlink := range xlinks {
		for _, ylink := range ylinks {
			if xlink == ylink {
				//并且在圆形范围内的
				// if math.Pow(float64(xlink.Entity.GetPosition().X-entity.GetPosition().X), 2)+
				// 	math.Pow(float64(xlink.Entity.GetPosition().Y-entity.GetPosition().Y), 2) <=
				// 	math.Pow(float64(radius), 2) {
				// 	entities = append(entities, xlink.Entity)
				// }
				entities = append(entities, xlink.Entity)
			}
		}
	}
	return entities
}
